package recursion;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Modified code taken from 
 * http://www.vogella.com/articles/JavaAlgorithmsTowersOfHanoi/article.html
 * 
 *  Timing complexity: O(2^n)
 *  Total steps required: 2^n - 1
 *  recurrence relationship: T(n) = 2*T(n-1) + 1 
 * 
 * */
public class TowersOfHanoi {
	
	// list to contain three towers
	private static List<Stack<Integer>> towers = new ArrayList<Stack<Integer>>(3);

	/**
	 * towers of hanoi algorithm implementation
	 * */
	public static void move(int n, int source, int target){
		if(n == 0){
			return;
		}
		
		int intermediate = 6 - source - target;
		move(n-1, source, intermediate);

		System.out.println("move disk no. "+n+" from "+source+" to "+target);		
		int poppedDisk = (towers.get(source - 1)).pop(); // extra code
		(towers.get(target - 1)).push(poppedDisk); // extra code
		
		move(n-1, intermediate, target);
	}
	
	
	/**
	 * main
	 * */
	public static void main(String[] args){
	
		// number of disks in source tower
		// number should be >= 0
		int noOfDisk = 3;
		
		// creates the tower and fill the source tower
		init(noOfDisk);
		
		// call recursive method
		move(noOfDisk, 1, 3);
		
		// print the results
		printResult();
	}
	
	/**
	 * Initializes the towers.
	 * It fills the source tower with given number of disk and creates
	 * empty intermediate and target tower.
	 * 
	 * @param  number of disks
	 * 
	 * */
	private static void init(int noOfDisk){
		// first tower
		Stack<Integer> sourceTower = new Stack<Integer>();
		for(int i = noOfDisk; i > 0; i--){
			sourceTower.push(i);
		}
		
		towers.add(sourceTower);
		towers.add(new Stack<Integer>()); // intermediate tower
		towers.add(new Stack<Integer>()); // target tower
	}
	
	/**
	 * Method to print the result
	 * 
	 * */
	private static void printResult(){
		System.out.println("source tower");
		Stack<Integer> sourceTower = towers.get(0);
		while(!sourceTower.isEmpty()){
			System.out.println(sourceTower.pop());
		}
		
		System.out.println("intermediate tower");
		Stack<Integer> intermediateTower = towers.get(1);
		while(!intermediateTower.isEmpty()){
			System.out.println(intermediateTower.pop());
		}
		
		System.out.println("target tower");
		Stack<Integer> targetTower = towers.get(2);
		while(!targetTower.isEmpty()){
			System.out.println(targetTower.pop());
		}		
	}	
} // end of class
